//二叉树的基本运算算法
#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 100
typedef char ElemType;


typedef struct node 
{	
	ElemType data;			//数据元素
	struct node *lchild;	//指向左孩子节点
	struct node *rchild;	//指向右孩子节点
} BTNode;


void CreateBTree(BTNode * &b,char *str)	//创建二叉树
{
	BTNode *St[MAXSIZE],*p=NULL;
	int top=-1,k,j=0;  
	char ch;
	b=NULL;				//建立的二叉树初始时为空
	ch=str[j];
	while (ch!='\0')  	//str未扫描完时循环
	{
		switch(ch) 
		{
			case '(':top++;St[top]=p;k=1; break;		//为左孩子节点
			case ')':top--;break;
			case ',':k=2; break;                      		//为孩子节点右节点
			default:p=(BTNode *)malloc(sizeof(BTNode));
			p->data=ch;p->lchild=p->rchild=NULL;
			if (b==NULL)                    	 	//*p为二叉树的根节点
				b=p;
			else  								//已建立二叉树根节点
			{	
				switch(k) 
				{
					case 1:St[top]->lchild=p;break;
					case 2:St[top]->rchild=p;break;
				}
			}
		}
		j++;
		ch=str[j];
	}
}
void DestroyBTree(BTNode *&b)
{	if (b!=NULL)
{	DestroyBTree(b->lchild);
	DestroyBTree(b->rchild);
	free(b);
}
}
BTNode *FindNode(BTNode *b,ElemType x) 
{
	BTNode *p;
	if (b==NULL)
		return NULL;
	else if (b->data==x)
		return b;
	else  
	{
		p=FindNode(b->lchild,x);
		if (p!=NULL) 
			return p;
		else 
			return FindNode(b->rchild,x);
	}
}

void DispBTree(BTNode *b) 
{
	if (b!=NULL)
	{	printf("%c",b->data);
		if (b->lchild!=NULL || b->rchild!=NULL)
		{	printf("(");						//有孩子节点时才输出(
			DispBTree(b->lchild);				//递归处理左子树
			if (b->rchild!=NULL) printf(",");	//有右孩子节点时才输出,
			DispBTree(b->rchild);				//递归处理右子树
			printf(")");						//有孩子节点时才输出)
		}
	}
}


typedef struct
{
	char path[MAXSIZE];
	int top;
} PATH;//类似栈的存储结构

PATH p9a3th;

int select(BTNode* t903, int k9e3y)//找到返回1，找不到返回0
{
	if (t903 == NULL)
	{
		return 0;
	}
	else
	{
		//将当前结点加入路径
		p9a3th.top++;
		p9a3th.path[p9a3th.top] = t903->data;
		if (t903->data == k9e3y)
		{
		//当前结点即为key，则返回1（找到）
			return 1;
		}
		else
		{
			//否则在左右继续寻找
			if (select(t903->lchild, k9e3y) || select(t903->rchild, k9e3y))
			{
				return 1;
			}
			else
			{
			//若没有找到，路径中移出结点，返回0（未找到）
				p9a3th.top--;
				return 0;
			}
		}
	}
}




int main()
{
	BTNode *b9a3;
	CreateBTree(b9a3,(char*)"A(B(D(,G)),C(E,F))");
	printf("b9a3: "); DispBTree(b9a3); printf("\n");
	char a9b3 = 'G';
	printf("要找的元素为：");
	scanf("%c",&a9b3);
	if(select(b9a3,a9b3)==0)
		printf("0");
	else
	{
		
		
		for(int i9a3 = 0;i9a3<p9a3th.top;i9a3++)
		{
			printf("%c ",p9a3th.path[i9a3]);
		}
	}

	
	
	DestroyBTree(b9a3);
	return 0;
}





